1. Field of the Invention
This invention relates to digital signature systems, and more specifically to cryptographic techniques involving the combination of a public-key digital signature with conventional techniques for cryptographic authentication.
2. Description of Prior Art
Reference is hereby made to P.C.T. publication WO 89/08957, E.P.O. filing 89905483.7, and U.S. Pat. No. 4,987,593, filed Mar. 16, 1988, titled "One-show blind signature systems," by the present applicant, which are incorporated herein by reference. Reference is also hereby made to E.P.O. filling 90200207.0 and U.S. Pat. No. 5,131,039, filed Jan. 29, 1990, titled "Optionally moderated transaction systems," by the present applicant, which are incorporated herein by reference.
A basic technique for "endorsing" a public key digital signature was disclosed in the first above included reference and a related paper presented at Crypto '88. This technique was used in the second above included reference and also in other subsequent publications, such as, for example, U.S. Pat. No. 5,016,274 by Micali et al related to a paper presented at Crypto '89 and CWI technical Report CS-R9035.
Endorsement schemes are simply one-time signature schemes where the authentication of the public key that is always needed in one time signature schemes is done using the very well know technique of a public key certificate.
Three efficiency improvements for the endorsement function, compared to that first disclosed in the first above included reference, are known in the prior art. The first two pertain to one-time signature schemes and the third improves the true public key digital signatures.
The first two improvements were made in the context of the well-know original one-time signatures called "Lamport" signatures that are disclosed and attributed to Lamport in "New directions in cryptography," IEEE Transaction on Information Theory, pp. 644, 654, 1976, and are also subsequently described by Lamport in SRI technical report CSL 98. Lamport signatures simply authenticate, as a public key, the output of a public one-way function on a list of secret values; later release of a subset of the secret values allows anyone to confirm both that they correspond to the authenticated list and the message signed by being encoded in the choice of subset.
The first improvement is believed disclosed at least in IBM Technical Disclosure Bulletin, vol. 28, No. 2, Jul. 1985, pp. 603-604, titled "Matrix digital signature for use with the data encryption algorithm" and in the Proceedings of Crypto '87 by Merklle in the context of Lamport signatures and was subsequently incorporated in the second above included reference by the present applicant. This first improvement reduces the size of the original list of secret inputs to the one-way function. Instead of simply basing the signature on single independent applications of one-way functions, the functions are composed or "chained" so that the output of the previous function application in the chain serves as the input of the next function application. Each chain can be thought of as representing one digit of the numeric message signed by the one-time scheme. The radix is one plus the length of the chain, with the original Lamport signatures having radix 2. This first improvement results in economy of storage and transmission, at the expense of an increase in computation.
The second efficiency improvement was also disclosed by Merkle, as cited above. It applies techniques, believed known in the coding art, that reduce the number of "control" digits needed. These digits prevent a signature from being changed into a signature on a different message. The previous disclosures cited used one control digit per message digit, with the control digit representing the additive inverse of the message digit. The improvement works essentially by having only a few control digits that represent the additive inverse of the sum of the message digits. Accordingly, the number of control digits is reduced from being linear in the number of message digits to being only logarithmic.
The third improvement applies to certain public key digital signature schemes. It was disclosed first in U.S. Pat. No. 4,949,380, in a paper presented at Crypto '89, PCT publication US89/04662, and EPO application 89912051.3, all substantially the same and all by the present applicant. This improvement allows plural public key signatures to be "intermingled" in the space taken by one, so long as they are made with coprime public exponents. They can be signed in the intermingled form, stored in that form, and later separated for showing. This technique also gives economy of storage (and communication), although potentially at the expense of extra computation.
One commercially interesting use of endorsement schemes appears to be in the area of "prepaid cards."
A prepaid smart card contains stored value which the person holding it can spend at retail points of payment. After accepting stored value from cards, retailers are periodically reimbursed with actual money by system providers. A system provider receives money in advance from people and stores corresponding value onto their cards. During each of these three kinds of transactions, secured data representing value is exchanged for actual money or for goods and services. Telephone cards used in France and elsewhere are probably the best known prepaid smart cards (though some phone cards use optical or magnetic techniques). National prepaid systems today typically aim to combine public telephones, merchants, vending, and public transportation. Automatic collection of road tolls may also be included soon.
Growth in the prepaid smart card market appears to be rapid. For instance, at the time of this application it is believed that national prepaid chipcard schemes are rolling out in Denmark, under construction in Portugal, and planned in Belgium, Spain, and France. The MAC network, believed the largest ATM network in the United States, has announced its entry, and systems are apparently already operational in South Africa and Switzerland.
In schemes based solely on conventional cryptography used by cards, secured modules (sometimes called SAM's) are needed at every point of payment. The reason is that transactions are consummated without communication with external sites, to keep transaction costs commensurate with the low-value of payments, and that conventional cryptographic authentication requires the communicants to share a common secret. Each secure module is believed to require the ability to develop secret keys of all cards, which gives some problems. If the cards of multiple system providers are to be accepted at the same point of payment, all the points of payment must have secured modules containing keys of every provider. This is believed to mean either a mutually trusted module containing the keys of multiple providers, which might be hard to achieve, or one module per provider, which becomes impractical as the number of providers grows. Furthermore, in any such system, if a module is penetrated, not only may significant retailer fraud be facilitated, but the entire card base may be compromised.
Endorsement schemes avoid these problems since they do not require such secured modules. Equipment at points of payment needs no secret keys, only public ones, in order to authenticate the endorsements, which act like guaranteed checks filled in with all the relevant details. These same endorsements can later be verified by the system provider for reimbursement. (While these systems allow full end-to-end verification, tamper-resistant aggregators can always be used for truncation.) They also allow the cards of any number of issuers to be accepted at all retailers; retailers cannot cheat issuers, and issuers cannot cheat each other.
The size of the chip in the card is of substantial practical importance in such systems. With a given technology, the more storage the more the chips cost to produce and the bigger they are. It is believed that in the industry larger chips are also thought to mean higher card production costs, and less reliable and durable cards. Cards announced so far for such national prepaid systems use only conventional cryptographic authentication and have only about one kilobyte of nonvolatile storage. For endorsement techniques to be competitive, it is believed important that they can be fit into the same chips. Prior art techniques do not allow enough endorsements to be stored in such chips.
Furthermore, it is believed that ordinary credit card and/or debit card transactions consummated using a smart card would benefit from the additional security of an off-line public key endorsement of their transaction details.